#define x(a) a.x
#define y(a) a.y
typedef double T;
const db eps = 1e-8;
const db pi = acos(-1.0);
int sign(db x) {return (x > eps)-(x < -eps);}

struct P {
	db x, y;
	P() {}
	P(db x, db y) {this->x = x;this->y = y;}
	P operator + (const P& c) const {return P(x + c.x, y + c.y);}
	P operator - (const P& c) const {return P(x - c.x, y - c.y);}
	P operator * (const db& c) const {return P(x * c, y * c);}
	P operator / (const db& c) const {return P(x / c, y / c);}
	bool operator < (const P& c) const {int f = sign(x - c.x); 
	return f ? f < 0 : sign(y - c.y) < 0;}
	bool operator == (const P& c) const {return !sign(x - c.x) && !sign(y - c.y);}
	bool operator != (const P& c) const {return !(*this == c);}
	bool operator > (const P& c) const {return !(*this == c) && !(*this < c);}
};

P read() {T x, y; scanf("%lf%lf", &x, &y); return P(x, y);}
T abs(P a) {return sqrt(x(a) * x(a) + y(a) * y(a));}
T norm(P a) {return x(a) * x(a) + y(a) * y(a);}
T dot(P a, P b) {return a.x * b.x + a.y * b.y;}
T cross(P a, P b) {return a.x * b.y - a.y * b.x;}
T disq(P a, P b) {return dot(b - a, b - a);}
T dis(P a, P b) {return sqrt(dot(b - a, b - a));}
T ang(P a, P b) {return atan2(y(b) - y(a), x(b) - x(a));}
T ang(P a, P o, P b) {return acos(dot(a - o, b - o) / abs(a - o) / abs(b - o));}
P rot(P a, T rad) {return P(x(a) * cos(rad) - y(a) * sin(rad), x(a) * sin(rad) + y(a) * cos(rad));}
P rot(P a,P o,T rad){return rot(a-o,rad)+o;}
P proj(P p,P v){return v*dot(p,v)/norm(v);}
P proj(P p,P a,P b){return (b-a)*dot(p-a,b-a)/norm(b-a)+a;} //点p在ab的投影点
P reflect(P p, P a, P b) {P o = proj(p,a,b); return o * 2 - p;} //求p关于ab对称点
P insLL(P p,P v,P q,P w) {P u = p - q; v = v - p; w = w - q; db t = cross(w, u) / cross(v, w); return p + v * t;}//直线交点
P rot90(P p) {return P(-y(p), x(p));}

bool onS(P p, P a, P b) { //判断点在线段上
	return sign(cross(p - a, b - a)) == 0 && sign(dot(p - a, p - b)) <= 0;
}

bool isLL(P a1, P a2, P b1, P b2) { //判断直线是否相交
	T c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1),
	  c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1);
	return sign(c1) * sign(c2) < 0 && sign(c3) * sign(c4) < 0;
}

bool isSS(P a1, P a2, P b1, P b2) { //判断线段是否相交
	T c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1),
	  c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1);
	return sign(max(x(a1), x(a2)) - min(x(b1), x(b2))) >= 0 &&
		sign(max(x(b1), x(b2)) - min(x(a1), x(a2))) >= 0 &&
		sign(max(y(a1), y(a2)) - min(y(b1), y(b2))) >= 0 &&
		sign(max(y(b1), y(b2)) - min(y(a1), y(a2))) >= 0 &&
		sign(c1) * sign(c2) <= 0 && sign(c3) * sign(c4) <= 0;
}

bool isLS(P a1, P a2, P b1, P b2) { //判断直线线段是否相交
	T c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
	return sign(c1) * sign(c2) <= 0;
}

db distoL(P p, P a, P b) {return fabs(cross(b - a, p - a)) / abs(b - a);}//p到直线ab距离

db distoS(P p, P a, P b) {//p到线段ab距离
	if (dot(b - a, p - a) < eps) return abs(p - a);
	if (dot(a - b, p - b) < eps) return abs(p - b);
	return distoL(p, a, b);
}

T areaP(P *p, int n) {//多边形面积
	T ans = 0;
	for (int i = 0; i < n; i++) ans += cross(p[i], p[i + 1]);
	return fabs(ans) / 2;
}

int Pinploy(P o, P *p, int n) { //判断点和多边形关系 -1边上0外1内
	int res = 0;
	for (int i = 0; i < n; i++) {
		P u = p[i], v = p[(i + 1) % n];
		if (onS(o, u, v)) return -1;
		int k = cross(v - u, o - u), d1 = sign(y(u) - y(o)), d2 = sign(y(v) - y(o));
		if (k > 0 && d1 <= 0 && d2 > 0) res++;
		if (k < 0 && d2 <= 0 && d1 > 0) res--;
	} return res != 0;
}

int convexhull(P *p, int n, P *ch) { //凸包
	sort(p, p + n); int m = 0;
	for (int i = 0; i < n; i++) {
		while (m > 1 && sign(cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2])) <= 0) m--;
		ch[m++] = p[i];
	} int k = m;
	for (int i = n - 2; i >= 0; i--) {
		while (m > k && sign(cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2])) <= 0) m--;
		ch[m++] = p[i];
	} if (n > 1) m--;
	return m;
}

struct C {P o;db r;C() {} C(P o, db r) : o(o), r(r) {}};

bool isLC(C c, P a, P b, P &p1, P &p2) { //线圆交点
	double x = dot(a - c.o, b - a), y = norm(b - a),
		   d = x * x - y * (norm(a - c.o) - c.r * c.r);
	if (sign(d) < 0) return false; if (d < 0) d = 0;
	P q1 = a - (b - a) * (x / y),
	  q2 = (b - a) * (sqrt(d) / y);
	p1 = q1 - q2, p2 = q1 + q2;
	return true;
}

bool isCC(C c1, C c2, P &p1, P &p2) {//圆圆交点
	db x = abs(c1.o - c2.o), 
	   y = ((c1.r * c1.r - c2.r * c2.r) / x + 1) / 2, 
	   d = c1.r * c1.r / x - y * y;
	if (sign(d) < 0) return false; if (d < 0) d = 0;
	P q1 = (c2.o - c1.o) * y + c1.o,
	  q2 = rot90((c2.o - c1.o) * sqrt(d));
	p1 = q1 - q2, p2 = q1 + q2;
	return true;
}

vector<P> tanCP(P p, C c) {//点圆切点
	db x = norm(p - c.o), d = x - c.r * c.r; vector<P> ans;
	if (sign(d) < 0) return ans; if (d < 0) d = 0;
	P q1 = (p - c.o) * (c.r * c.r / x),
	  q2 = rot90((p - c.o) * (-c.r * sqrt(d) / x));
	ans.pb(c.o + q1 - q2); ans.pb(c.o + q1 + q2);
	return ans;
}

vector<pair<P, P> > tanCC(C c1, C c2) {//圆圆切线
	vector<pair<P, P> > ans;
	if (!sign(c1.r - c2.r)) {
		P dir = c2.o - c1.o;
		dir = rot90(dir * (c1.r / abs(dir)));
		ans.pb(mp(c1.o + dir, c2.o + dir));
		ans.pb(mp(c1.o - dir, c2.o - dir));
	} else {
		P p = (c1.o * (-c2.r) + c2.o * c1.r) / (c1.r - c2.r);
		vector<P> ps = tanCP(p, c1), qs = tanCP(p, c2);
		for (int i = 0; i < sz(ps) && i < sz(qs); i++) {
			if (!i || (ps[i] != ps[i - 1] && qs[i] != qs[i - 1]))
				ans.pb(mp(ps[i], qs[i]));
		}
	}
	P p = (c1.o * c2.r + c2.o * c1.r) / (c1.r + c2.r);
	vector<P> ps = tanCP(p, c1), qs = tanCP(p, c2);
	for (int i = 0; i < sz(ps) && i < sz(qs); i++) {
		if (!i || (ps[i] != ps[i - 1] && qs[i] != qs[i - 1]))
			ans.pb(mp(ps[i], qs[i]));
	}
	return ans;
}

db areaCC(C c1, C c2) {//圆面积交
	double d = abs(c1.o - c2.o);
	if (sign(c1.r + c2.r - d) <= 0) return 0;
	if (sign(d - fabs(c1.r - c2.r)) <= 0) {
		double r = min(c1.r, c2.r);
		return r * r * pi;}
	double x = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d),
		   t1 = acos(x / c1.r), t2 = acos((d - x) / c2.r);
	return c1.r * c1.r * t1 + c2.r * c2.r * t2 - d * c1.r * sin(t1);
}

db areaCT(double r, P p1, P p2) {//圆三角形面积交
	P q1, q2, O = P(0, 0); C c = C(P(0.0, 0.0), r); 
	int f = isLC(c, p1, p2, q1, q2);
	if (!f) return r * r * ang(p1, O, p2) / 2;
	bool b1 = sign(abs(p1) - r) > 0, b2 = sign(abs(p2) - r) > 0;
	if (b1 && b2) {
		if (sign(dot(p1 - q1, p2 - q1)) <= 0 && sign(dot(p1 - q2, p2 - q2)) <= 0)
			return (r * r * (ang(p1, O, p2) - ang(q1, O, q2)) + fabs(cross(q1, q2))) / 2;
		else return r * r * ang(p1, O, p2) / 2;
	} else if (b1) return (r * r * ang(p1, O, q1) + fabs(cross(q1, p2))) / 2;
	else if (b2) return (r * r * ang(q2, O, p2) + fabs(cross(p1, q2))) / 2;
	else return fabs(cross(p1, p2)) / 2;
}

P inC(P A, P B, P C) {//内心
	db a = abs(B - C), b = abs(C - A), c = abs(A - B);
	return (A * a + B * b + C * c) / (a + b + c);
}

P outC(P A, P B, P C) {//外心
	P b = B - A, c = C - A;
	db dB = norm(b), dC = norm(c), d = 2 * cross(b, c);
	return A - P(y(b) * dC - y(c) * dB, x(c) * dB - x(b) * dC) / d;
}

P othroC(P A, P B, P C) {//垂心
	P ba = B - A, ca = C - A, bc = B - C;
	db Y = y(ba) * y(ca) * y(bc),
		a = x(ca) * y(ba) - x(ba) * y(ca),
		xx = (Y + x(ca) * y(ba) * x(B) - x(ba) * y(ca) * x(C)) / a,
		yy = -x(ba) * (xx - x(C)) / y(ba) + y(ca);
	return P(xx, yy);
}

void Mincir(P *p, int n) {//最小圆覆盖
	random_shuffle(p, p + n);
	P cir = p[0]; db r = 0;
	for (int i = 1; i < n; i++) {
		if (sign(dis(cir, p[i]) - r) <= 0) continue;
		cir = p[i], r = 0;
		for (int j = 0; j < i; j++) {
			if (sign(dis(cir, p[j]) - r) <= 0) continue;
			cir = P((x(p[i]) + x(p[j])) / 2, (y(p[i]) + y(p[j])) / 2);
			r = dis(cir, p[j]);
			for (int k = 0; k < j; k++) {
				if (sign(dis(cir, p[k]) - r) <= 0) continue;
				cir = outC(p[i], p[j], p[k]);
				r = dis(cir, p[k]);
	}}} printf("%.2f %.2f %.2f\n", x(cir), y(cir), r);
}

//半平面交
const int N = 450005;
struct Seg {
	P s, e;
	double r;
	void getr() {r = atan2(y(e)-y(s), x(e)-x(s));}
	bool operator < (const Seg& c) const {
		int d = sign(r - c.r);
		if (!d) return sign(cross(c.s - s, c.e - s)) > 0;
		return d < 0;
	}
} seg[N], Q[N];
int sz; //初始化sz = 0

P insLL(Seg a, Seg b) {return insLL(a.s,a.e,b.s,b.e);}

void add_seg(db xa, db ya, db xb, db yb) {
	seg[sz].s = P(xa,ya); seg[sz].e = P(xb,yb);
	seg[sz].getr(); sz++;
}

int hpi(P *p) {
	sort(seg,seg+sz);
	int tmp=1;
	for (int i=1;i<sz;i++)
		if (sign(seg[i].r-seg[tmp-1].r))
			seg[tmp++]=seg[i];
	sz=tmp; Q[0]=seg[0];Q[1]=seg[1];
	int h=0,r=1;
	for (int i=2;i<sz;i++) {
		while(h<r&&sign(cross(seg[i].e-seg[i].s,insLL(Q[r],Q[r-1])-seg[i].s))<=0) r--;
		while(h<r&&sign(cross(seg[i].e-seg[i].s,insLL(Q[h],Q[h+1])-seg[i].s))<=0) h++;
		Q[++r]=seg[i];
	}
	while(h<r&&sign(cross(Q[h].e-Q[h].s,insLL(Q[r],Q[r-1])-Q[h].s))<=0) r--;
	while(h<r&&sign(cross(Q[r].e-Q[r].s,insLL(Q[h],Q[h+1])-Q[r].s))<=0) h++;
	if (h+1>=r) return 0;
	int m = 0;
	for (int i=h;i<r;i++) p[m++]=insLL(Q[i],Q[i+1]);
	if (r>h+1) p[m++]=insLL(Q[h],Q[r]);
	return m;
}

//k圆面积交
struct Event {
	P p;
	db ang;
	int delta;
	Event() {}
	Event (P p=P(0,0), db ang = 0, int delta=0) : p(p), ang(ang), delta(delta) {}
	bool operator < (const Event& c) const {return ang < c.ang;}
};

db sqr(db x) {return x * x;}

void addEvent(C a, C b, vector<Event> &evt, int&cnt) {
	db d2 = norm(a.o-b.o),
	   dRatio = ((a.r-b.r) * (a.r + b.r) / d2 + 1) / 2,
	   pRatio = sqrt(-(d2 - sqr(a.r - b.r)) * (d2 - sqr(a.r + b.r)) / (d2 * d2 * 4));
	P d = b.o - a.o, p = rot(d, pi / 2),
	  q0 = a.o + d * dRatio + p * pRatio,
	  q1 = a.o + d * dRatio - p * pRatio;
	db ang0 = ang(a.o, q0), ang1 = ang(a.o, q1);
	evt.pb(Event(q1,ang1,1)); evt.pb(Event(q0,ang0,-1));
	cnt += ang1 > ang0;
}

bool issame(C a, C b) {return !sign(abs(a.o - b.o)) && !sign(a.r - b.r);}
bool overlap(C a, C b) {return sign(a.r - b.r - abs(a.o - b.o)) >= 0;}
bool intersect(C a, C b) {return sign(abs(a.o - b.o) - a.r - b.r) < 0;}

const int N = 2005;
void solve(C *c, int n, db *ans) {
	memset(ans, 0, sizeof(db) * (n + 2));
	for (int i = 0; i < n; i++) {
		int cnt = 1;
		vector<Event> evt;
		for (int j = 0; j < i; j++) if (issame(c[i], c[j])) ++cnt;
		for (int j = 0; j < n; j++)
			if (j != i && !issame(c[i], c[j]) && overlap(c[j], c[i]))
				cnt++;
		for (int j = 0; j < n; j++)
			if (j != i && !overlap(c[j], c[i]) && !overlap(c[i], c[j]) && intersect(c[i], c[j]))
				addEvent(c[i], c[j], evt, cnt);
		if (!sz(evt)) ans[cnt] += pi * c[i].r * c[i].r;
		else {
			sort(evt.begin(), evt.end());
			evt.pb(evt.front());
			for (int j = 0; j + 1 < sz(evt); j++) {
				cnt += evt[j].delta;
				ans[cnt] += cross(evt[j].p, evt[j + 1].p) / 2;
				db ang = evt[j + 1].ang - evt[j].ang;
				if (ang < 0) ang += pi * 2;
				ans[cnt] += ang * c[i].r * c[i].r / 2 - sin(ang) * c[i].r * c[i].r / 2;
	}}}
}

//k凸包面积交
const int N = 1005;
struct Rect {
	P d[10];
	int dn;
	P operator [] (const int &n) {return d[n];}
	void read() {
		for (int i = 0; i < dn; i++) scanf("%lf%lf", &x(d[i]), &y(d[i]));
		d[dn] = d[0];
	}
} r[N];

int n;
typedef double db;
typedef pair<db, int> pdi;
pdi res[1000005];

db getLoc(P a, P b, P p) {
	if (sign(x(b) - x(a))) return (x(p) - x(a)) / (x(b) - x(a));
	return (y(p) - y(a)) / (y(b) - y(a));
}

db work() {
	db rt = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < r[i].dn; j++) {
			int sz = 0;
			res[sz++] = pdi(0, 0); res[sz++] = pdi(1, 0);
			for (int t = 0; t < n; t++) {
				if (t == i) continue;
				for (int g = 0; g < r[t].dn; g++) {
					int du = sign(cross(r[i][j + 1] - r[i][j], r[t][g] - r[i][j]));
					int dv = sign(cross(r[i][j + 1] - r[i][j], r[t][g + 1] - r[i][j]));
					if (!du && !dv) {
						if (sign(dot(r[i][j + 1] - r[i][j], r[t][g + 1] - r[t][g])) < 0 || i < t) {
							res[sz++] = pdi(getLoc(r[i][j], r[i][j + 1], r[t][g]), 1);
							res[sz++] = pdi(getLoc(r[i][j], r[i][j + 1], r[t][g + 1]), -1);
						}
					}
					else {
						db s1 = cross(r[i][j] - r[t][g], r[t][g + 1] - r[t][g]);
						db s2 = cross(r[t][g + 1] - r[t][g], r[i][j + 1] - r[t][g]);
						if (du >= 0 && dv < 0) res[sz++] = pdi(s1 / (s1 + s2), 1);
						else if (du < 0 && dv >= 0) res[sz++] = pdi(s1 / (s1 + s2), -1);
					}
				}
			}
			sort(res, res + sz);
			int cnt = 0; sz--;
			for (int t = 0; t < sz; t++) {
				cnt += res[t].se;
				if (cnt == 0 && sign(res[t].fi - res[t + 1].fi)) {//修改cnt可求k面积覆盖
					double a = res[t].fi;
					if (a < 0) a = 0; if (a > 1) break;
					double b = res[t + 1].fi;
					if (b < 0) continue; if (b > 1) b = 1;
					rt += cross((r[i][j + 1] - r[i][j]) * a + r[i][j], (r[i][j + 1] - r[i][j]) * b + r[i][j]);
				}
			}
		}
	return rt / 2;
}

//快速凸包询问
const int INF = 1000000000; //INF 为坐标范围 , 需要定义点类大于号
struct Convex {
	int n;
	vector<P> a, upper, lower;
	Convex(vector<P> _a) : a(_a) {
		//构造函数时传入凸包要求无重点 , 面积非空 , 以pair(x,y) 的最小点放在第一个
		n = a.size(); int ptr = 0;
		for(int i = 1; i < n; ++ i) if (a[ptr] < a[i]) ptr = i;
		for(int i = 0; i <= ptr; ++ i) lower.push_back(a[i]);
		for(int i = ptr; i < n; ++ i) upper.push_back(a[i]);
		upper.push_back(a[0]);
	}
	//改成实数只需修改 sign 函数,以 把 long long 改为 double 即可
	int sign(long long x) { return x < 0 ? -1 : x > 0; }
	pair<long long, int> get_tangent(vector<P> &convex, P vec) {
		int l = 0, r = (int)convex.size() - 2;
		for( ; l + 1 < r; ) {
			int mid = (l + r) / 2;
			if (sign(cross(convex[mid + 1] - convex[mid], vec)) > 0) r = mid;
			else l = mid;
		}
		return max(make_pair(cross(vec, convex[r]), r), make_pair(cross(vec, convex[0]), 0));
	}
	void update_tangent(const P &p, int id, int &i0, int &i1) {
		if (cross(a[i0] - p, a[id] - p) > 0) i0 = id;
		if (cross(a[i1] - p, a[id] - p) < 0) i1 = id;
	}
	void binary_search(int l, int r, P p, int &i0, int &i1) {
		if (l == r) return;
		update_tangent(p, l % n, i0, i1);
		int sl = sign(cross(a[l % n] - p, a[(l + 1) % n] - p));
		for( ; l + 1 < r; ) {
			int mid = (l + r) / 2;
			int smid = sign(cross(a[mid % n] - p, a[(mid + 1) % n] - p));
			if (smid == sl) l = mid; else r = mid;
		}
		update_tangent(p, r % n, i0, i1);
	}
	int binary_search(P u, P v, int l, int r) {
		int sl = sign(cross(v - u, a[l % n] - u));
		for( ; l + 1 < r; ) {
			int mid = (l + r) / 2, smid = sign(cross(v - u, a[mid % n] - u));
			if (smid == sl) l = mid; else r = mid;
		}
		return l % n;
	}
	bool contain(P p) { //判定点是否在凸包内,在边界返回 true
		if (p.x < lower[0].x || p.x > lower.back().x) return false;
		int id = lower_bound(lower.begin(), lower.end(), P(p.x, -INF)) - lower.begin();
		if (lower[id].x == p.x) {
			if (lower[id].y > p.y) return false;
		} else if (cross(lower[id - 1] - p, lower[id] - p) < 0) return false;
		id = lower_bound(upper.begin(), upper.end(), P(p.x, INF), greater<P>()) - upper.begin();
		if (upper[id].x == p.x) {
			if (upper[id].y < p.y) return false;
		} else if (cross(upper[id - 1] - p, upper[id] - p) < 0) return false;
		return true;
	}

	// 求点p关于凸包的两个切点,如果在凸包外则有序返回编号,共线的多个切点返回任意一个,否则返回false
		bool get_tangent(P p, int &i0, int &i1) {
			if (contain(p)) return false; i0 = i1 = 0;
			int id = lower_bound(lower.begin(), lower.end(), p) - lower.begin();
			binary_search(0, id, p, i0, i1);
			binary_search(id, (int)lower.size(), p, i0, i1);
			id = lower_bound(upper.begin(), upper.end(), p, greater<P>()) - upper.begin();
			binary_search((int)lower.size() - 1, (int)lower.size() - 1 + id, p, i0, i1);
			binary_search((int)lower.size() - 1 + id, (int)lower.size() - 1 + (int)upper.size(), p, i0, i1);
			return true;
		}

	// 求凸包上和向量 vec 叉积最大的点,返回编号,共线的多个切点返回任意一个
		int get_tangent(P vec) {
			pair<long long, int> ret = get_tangent(upper, vec);
			ret.second = (ret.second + (int)lower.size() - 1) % n;
			ret = max(ret, get_tangent(lower, vec));
			return ret.second;
		}

	// 求凸包和直线 u,v 的交点 , 如果无严格相交返回 false. 如果有则是和 (i,next(i)) 的交点, 两个点无序 , 交在点上不确定返回前后两条线段其中之一
		bool get_intersection(P u, P v, int &i0, int &i1) {
			int p0 = get_tangent(u - v), p1 = get_tangent(v - u);
			if (sign(cross(v - u, a[p0] - u)) * sign(cross(v - u, a[p1] - u)) < 0) {
				if (p0 > p1) swap(p0, p1);
				i0 = binary_search(u, v, p0, p1);
				i1 = binary_search(u, v, p1, p0 + n);
				return true;
			} else return false;
		}
};
